package com.gxc.array;

/**
 * 给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器
 * 请返回容器能装多少水
 * 比如，arr = {3，1，2，5，2，4}，根据值画出的直方图就是容器形状，该容器可以装下5格水
 * 再比如，arr = {4，5，1，3，2)，该容器可以装下2格水
 *
 */
public class Container {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            int[] random = random();
            if (holdWater(random) != holdWater2(random)) {
                println(random);
                System.out.println("算法有问题");
                break;
            }
        }

        int[] arr = new int[]{3,1, 2, 5, 2, 4};
        System.out.println(holdWater(arr));
        System.out.println(holdWater2(arr));
        arr = new int[]{4, 5, 1, 3, 2};
        System.out.println(holdWater(arr));
        System.out.println(holdWater2(arr));
    }

    /**
     * 时间复杂度还是O(N)，额外空间复杂度是O(N)
     * 遍历记录当前位置左右的最高值，如果左右的最高值都比当前高，则当前位置一定能装水。装水量等于左右最高值中较小的-当前的高度，
     * 否则当前位置则装不了水。
     * 构建两个预处理数组记录当前位置的左右最高值，然后遍历取每个位置的装水值相加即可
     * @param array
     * @return
     */
    public static int holdWater(int[] array) {
        int[] leftMax = new int[array.length];
        int[] rightMax = new int[array.length];

        int lmax = 0;
        int rmax = 0;
        //当前位置左边的最高值
        for (int i = 0; i < array.length; i++) {
            leftMax[i] = lmax;
            lmax = Math.max(array[i], lmax);
        }
        //当前位置右边的最高值
        for (int i = array.length-1; i >= 0; i--) {
            rightMax[i] = rmax;
            rmax = Math.max(array[i], rmax);
        }

        int sum = 0;
        //遍历取每个位置的装水值
        for (int i = 0; i < array.length; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            sum += min>array[i] ? (min - array[i]):0;
        }
        return sum;
    }

    /**
     * 时间复杂度还是O(N)，额外空间复杂度是O(1)
     * 上面空间复杂度是O(N)使用数组来记录每个位置的左右最高值，优化为：
     * 设置四个变量，
     * left,right
     * leftmax左边高度最大值 和rightmax高度最大值
     * left从左开始移动,right 从右开始移动
     * 由于当前位置的盛水由左右最大高度的小值决定，leftmax和rightmax 谁小,
     * 计算小值的left 和right位置
     * left 和right 谁移动（因为当前位置的盛水由左右最大高度的小值决定，
     * 所以另一边就算有更大的高度，也不算影响盛水量）,同时更新leftmax和rightmax的小值
     * @param array
     * @return
     */
    public static int holdWater2(int[] array) {
        int sum = 0;
        int left = 1;
        int right = array.length-2;
        int leftMax = 0;
        int rightMax = array.length-1;

        while (left<=right) {
            if (array[leftMax]<=array[rightMax]) {
                if (array[left]<array[leftMax]) {
                    sum += array[leftMax]-array[left];
                } else {
                    leftMax = left;
                }
                left++;
            } else if (array[leftMax]>array[rightMax]) {
                if (array[right]<array[rightMax]) {
                    sum += array[rightMax]-array[right];
                } else {
                    rightMax = right;
                }
                right--;
            }
        }
        return sum;
    }

    private static int[] random() {
        int size = (int) (Math.random()*10)+1;
        int[] arr = new int[size];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*10+1);
        }
        return arr;
    }

    private static void println(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }

}
